'''#遍历二叉树,属于深度优先，每个节点访问三次
'''
class Node:
    def __init__(self, data):
        self.value = data
        self.left = None
        self.right = None
# def preOrderRecur(head: Node):
#     if not head : return
#     print(f'{head.value}' + " ")
#     preOrderRecur(head.left)
#     preOrderRecur(head.right)
# def inOrderRecur(head: Node):
#     if not head : return
#     preOrderRecur(head.left)
#     print(f'{head.value}' + " ")
#     preOrderRecur(head.right)

'''
折纸问题 【题目】 请把一段纸条竖着放在桌子上，然后从纸条的下边向 上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕 突起的方向指向纸条的背面。
如果从纸条的下边向上方连续对折 2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折 痕、下折痕和上折痕。 
给定一 个输入参数N，代表纸条都从下边向上方连续对折N次， 请从上到下打印所有折痕的方向。 
例如：N=1时，打印： down N=2时，打印： down down up
'''
# 每次折痕都在上次折痕的上下两边分别出现两个，上边是凹（down）,下边是凸（up)

def printAllFolds(N: int) :
    printProcess(1, N, True)
###根中序遍历类似
def printProcess(i: int, N: int, down: bool):
    if (i > N) : return
    printProcess(i + 1, N, True)  #左子树头都是down
    print('down' if down else 'up')
    printProcess(i + 1, N, False) ##右子树头都是up

def main(): 
    N = 4
    printAllFolds(N)

main()
# def posOrderRecur(head: Node):
#     if not head : return
#     preOrderRecur(head.left)
#     preOrderRecur(head.right)   
#     print(f'{head.value}' + " ")

# 使用三个节点模拟下试试
# def preOrderUnRecur(head: Node):
#     if not head : return
#     print("pre-order: ")
#     if head :
#         stack = []
#         stack.append(head)
#         while len(stack) > 0:
#             head = stack.pop()
#             print(f'{head.value}' + " ")
#             if head.right:
#                 stack.append(head.right) # 先押入右
#             if head.left:
#                 stack.append(head.left)  # 再押入右

#当把左边界都压入，弹出就是：先弹左再弹中
# def inOrderUnRecur(head: Node):
#     print("in-order: ")
#     if head:
#         stack = []
#         while len(stack) > 0 or head :
#             if head: # 先把左边都遍历完
#                 stack.append(head)
#                 head = head.left
#             else :
#                 head = stack.pop()  # 前面看到，head为空，从栈拿一个节点，打印，当前节点变到右，
#                 print(f'{head.value}' + " ")
#                 head = head.right  
# 左-右-中， 后序遍历非递归版， 由于人工模拟的栈只有到达每个节点两次，不能像自动栈那样，到达三次，又由于后序遍历需要再到达节点第三次时打印，
# 所以需要借助两个栈实现       
# def posOrderUnRecur1(head: Node):
#     print("pos-order: ")
#     if head :
#         s1 = []
#         s2 = []
#         s1.append(head)
#         while len(s1) > 0:
#             head = s1.pop()
#             s2.append(head)
#             if head.left :
#                 s1.append(head.left)
#             if head.right :
#                 s1.append(head.right)       
#         while len(s2) > 0:
#             print(f'{s2.pop().value}' + " ")     
'''
c == current, h == last c
'''
# def posOrderUnRecur2(h: Node) :
#     print("pos-order: ")
#     if h :
#         stack = []
#         stack.append(h)
#         c = None
#         while len(stack) > 0:
#             c = stack[-1]
#             if c.left and h != c.left and h != c.right:
#                 stack.append(c.left)   # 先处理c的左树， c是新节点压入
#             elif c.right and h != c.right:
#                 stack.append(c.right)  # 再处理c的右树，c的左处理完了，开始处理右边
#             else:
#                 print(f'{stack.pop().value}' + " ")
#                 h = c   # 再处理c, h始终指向c上次打印的，c左右都处理完了，打印c

# def main():
#     head = Node(5)
#     head.left = Node(3)
#     head.right = Node(8)
#     head.left.left = Node(2)
#     head.left.right = Node(4)
#     head.left.left.left = Node(1)
#     head.right.left = Node(7)
#     head.right.left.left = Node(6)
#     head.right.right = Node(10)
#     head.right.right.left = Node(9)
#     head.right.right.right = Node(11)   
#     # recursive
#     print("==============recursive==============")
#     print("pre-order: ")
#     preOrderRecur(head)
#     print()
#     print("in-order: ")
#     inOrderRecur(head)
#     print()
#     print("pos-order: ")
#     posOrderRecur(head)
#     print()    
#     # unrecursive
#     print("============unrecursive=============")
#     preOrderUnRecur(head)
#     inOrderUnRecur(head)
#     posOrderUnRecur1(head)
#     posOrderUnRecur2(head)

#打印二叉树 ， 右 中 左的遍历方式
def getSpace(num: int) -> str:
    # return f'|{" "*num}|'
    return f'|{" "*num}|'

def printInOrder(head: Node, height: int, to: int, length: int):
    if not head :  return
    printInOrder(head.right, height + 1, "v", length)  #右
    val = to + str(head.value) + to
    lenM = len(val)
    lenL = (length-lenM) >> 1
    lenR = length - lenM - lenL
    val = getSpace(lenL) + val + getSpace(lenR)
    print(getSpace(height * length) + val)
    printInOrder(head.left, height + 1, "^", length)    #左


def printTree(head: Node) :
    print("Binary Tree:")
    printInOrder(head, 0, "H", length=17) # head在0层，它的左孩子是'^' 它的右孩子是'V'， 17是node.value 的长度

import sys

def main():
    head = Node(1)
    head.left = Node(-222222222)
    head.right = Node(3)
    head.left.left = Node(-sys.maxsize)
    head.right.left = Node(55555555)
    head.right.right = Node(66)
    head.left.left.right = Node(777)
    printTree(head) 

    head = Node(1)
    head.left = Node(2)
    head.right = Node(3)
    head.left.left = Node(4)
    head.right.left = Node(5)
    head.right.right = Node(6)
    head.left.left.right = Node(7)
    printTree(head)  
      
    head = Node(1)
    head.left = Node(1)
    head.right = Node(1)
    head.left.left = Node(1)
    head.right.left = Node(1)
    head.right.right = Node(1)
    head.left.left.right = Node(1)
    printTree(head)






if __name__ == '__main__':
    main()
'''
#查找后继节点,中序遍历中，一个节点的下一个节点
# 1. 右子树的最左节点
# 2. 从下往上找，一直找到某个节点是父节点的左节点

# 前驱
# 1.左子树的最右节点
# 2. 从下往上找，一直找到某个节点是父节点的右节点
'''
class Node :
    def __init__(self, data) -> None:
        self.value = data
        self.left = None
        self.right = None
        self.parent = None

def getLeftMost(node: Node) -> Node:
    if not node : return node
    while node.left :
        node = node.left
    return node

def getSuccessorNode(node: Node) -> Node:
    if not node : return node
    if node.right : #右子树的最左节点
        return getLeftMost(node.right)
    else :
        parent = node.parent
        while parent and parent.left != node: # 当父节点的左不是当前节点时，继续找
            node = parent
            parent = node.parent
        return parent

def main():
    head =  Node(6)
    head.parent = None
    head.left =  Node(3)
    head.left.parent = head
    head.left.left =  Node(1)
    head.left.left.parent = head.left
    head.left.left.right =  Node(2)
    head.left.left.right.parent = head.left.left
    head.left.right =  Node(4)
    head.left.right.parent = head.left
    head.left.right.right =  Node(5)
    head.left.right.right.parent = head.left.right
    head.right =  Node(9)
    head.right.parent = head
    head.right.left =  Node(8)
    head.right.left.parent = head.right
    head.right.left.left =  Node(7)
    head.right.left.left.parent = head.right.left
    head.right.right =  Node(10)
    head.right.right.parent = head.right   
    test = head.left.left
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.left.left.right
    if test and getSuccessorNode(test): print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.left
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.left.right
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.left.right.right
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.right.left.left
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.right.left
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.right
    if test and getSuccessorNode(test):  print(f'{test.value}' + " next: " + f'{getSuccessorNode(test).value}')
    test = head.right.right # 10's next is None
    if test : print(f'{test.value}' + " next: " + "None")
    
main()